#include <stdio.h>
#include <stdlib.h>

// 不带头结点  front指向队头元素 rear指向队尾元素

struct LNode
{
    int data;
    struct LNode *next;
};

typedef struct // 链式队列
{
    LNode *front, *rear;  // 队尾队头指针
    // int len;

}LinkQueue;

// --------------------------------------

void InitQueue(LinkQueue &LQ)
{
    LQ.front = NULL;
    LQ.rear = NULL;
}

bool isEmpty(LinkQueue &LQ)
{
    return LQ.front == NULL;
}

bool EnQueue(LinkQueue &LQ, int x)
{
    LNode *n = (LNode *)malloc(sizeof(LNode));
    n->next = NULL;
    n->data = x;

    if(isEmpty(LQ))  // 首位元素入队 队头指针也指向第一个元素
    {
        LQ.front = n; 
        LQ.rear = n;
    }
    LQ.rear->next = n;  // 队尾入队
    LQ.rear = n;

    return true;
    
}

bool DeQueue(LinkQueue &LQ, int &x)
{
    if(isEmpty(LQ))
    {
        return false;
    }

    LNode *p;
    p = LQ.front;
    x = p->data;

    LQ.front = p->next;
    if(LQ.rear == p)  // 最后一个元素出队
    {
        LQ.front = NULL;
        LQ.rear = NULL;
    }
    free(p);
    return true;
}
